package org.algorithm.二师兄.数组.三月.第二周;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/06 9:38 PM  周三题目
 * @description: 前缀和
 *
 *  <p>
 *      你和一群强盗准备打劫银行。给你一个下标从 0开始的整数数组security，其中security[i]是第 i天执勤警卫的数量。日子从 0开始编号。同时给你一个整数time。
 *
 *      如果第 i天满足以下所有条件，我们称它为一个适合打劫银行的日子：
 *      第 i天前和后都分别至少有 time天。
 *      第 i天前连续 time天警卫数目都是非递增的。
 *      第 i天后连续 time天警卫数目都是非递减的。
 *      更正式的，第 i 天是一个合适打劫银行的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
 *
 *      请你返回一个数组，包含 所有 适合打劫银行的日子（下标从 0开始）。返回的日子可以 任意顺序排列。
 *  </p>
 * 参考题解： https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/solution/gong-shui-san-xie-qian-zhui-he-yun-yong-gf604/
 * uri： https://leetcode-cn.com/problems/find-good-days-to-rob-the-bank/
 */
public class 适合打劫银行的日子 {
    public static void main(String[] args) {
        int[] nums = {5,3,3,3,5,6,2};
        System.out.println(goodDaysToRobBank(nums, 2));
    }
    public static List<Integer> goodDaysToRobBank(int[] security, int time) {
        // time 在   time -> security.length - time  之间
        int n = security.length;
        List<Integer> result = new ArrayList<>();
        // 如果time为0， 则每天都适合抢
        if (time == 0) {
            for (int i = 0; i < n; i++) {
                result.add(i);
            }
            return result;
        }
        // 对每个元素都去遍历一遍， true适合抢， false不适合
        boolean[] salt = new boolean[n];
        int left = 0, right = 0;
        //双指针遍历
        for (int i = 1; i < n; i++) {
            if (security[i - 1] >= security[i]) {
                left++;
            }else {
                left = 0;
            }
            if (left >= time) {
                salt[i] = true;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (security[i] <= security[i + 1]) {
                right++;
            }else {
                right = 0;
            }
            if (right < time && salt[i]) {
                salt[i] = false;
            }
        }

        for (int i = time; i < n - time; i++) {
            if (salt[i]) {
                result.add(i);
            }
        }
        return result;
    }
}
